Entities that provide computing resources over a communication network may allow a client to use, possibly for a fee, a certain amount of computing capacity on a computer system remote from a computing environment of the client. For example, a client may submit a request to create and operate a virtual machine running on a host server of the provisioned computing environment provider. Host computing systems on which to instantiate instances of computing capacity are typically chosen at random.